On the one-sided and two-sided similarities or weak similarities of permutations

On the one-sided and two-sided similarities or weak
similarities of permutations

Bau-Sen Du

Institute of Mathematics
Academia Sinica
Taipei 11529, Taiwan
dubs@math. sinica.edu. tw

Abstract

Let n > 3 be an integer. Let Pn = {1,2,3, ■■ ■ ,n — 1, n} and let Sn be the symmetric
group of permutations on P„. Motivated by the theory of discrete dynamical systems on
the interval, we associate each permutation an in Sn a (zero-one) Petrie matrix Mrj„,n-i in
GL{n—l, R) (which is generally not the same as the usual permutation matrix). Then, for
any two permutations an and pn in Sn, the notions of right, left and two-sided similarities
(and weak similarities respectively) of an and pn are introduced using the similarities (and
the characteristic polynomials respectively) of the correspnding Petrie matrices of some
extended permutations related to an and pn and examples are presented. As a by-product,
we obtain ways to construct countably infinitely many pairs of Petrie matrices which are
similar.

1 Introduction

For every positive integer i, we shall always let Jj = + 1] and, for every integer m > 2, we
shall always let W^m = <| ^ Jj : G F, 1 < i < m j- be the m-dimensional vector space over
the field F with = {^j : 1 < < iti} as a (standard) basis. For convenience, for integers

k-l

1 < j < A; < m + 1, we let [j,k] denote the element Ji i^i W^m.. Let n > 3 be a fixed

i=j

integer and let P„ be the set of all integers in [l,n]. Let cr be a map from P„ into itself such
that 7^ a{i + 1) for all 1 < i < n — 1. The map a defines a linear transformation, which

/n-l \ n-l

will always be denoted as from PV^n-i into itself such that (pa[ ^ r^Jj 1 = ^ ri(p„[Ji),

1=1 / 1=1

1

(T(i+1)-1

where (pa{Ji) = Yl Jj ^(^) < ^(^ + 1) ^'^'^ '{'ai.Ji) = X] ^(^ + 1) < ^(0- Let

j=o-(i) j=o-(j+l)

-^(T,n-i = (o-ij) be the (n — 1) x (n — 1) matrix defined by = 1 for all di < j < (3i — 1, where
ttj = min{(T(i), a{i + 1)} and = max{cr(i), cr(2 + 1)}, and aij = elsewhere. Note that, when
(T is a permutation, this matrix Mo-^„_i need not be the same as the usual permutation matrix.
It is clear that such matrices Mo-,„_i have entries either zeros or ones such that the ones in
each row occur consecutively. For our purpose, we define a Petrie matrix to be a square matrix
whose entries are either zeros or ones such that the ones in each row occur consecutively. The
determinant of a Petrie matrix is known |15| and easily seen (by induction) to be either or ±1.
So, the matrix M„^n-i induced by the map a on P„ is a square Petrie matrix. We shall call this
matrix Mo-^^-i the Petrie matrix of a. It is easy to see that, with respect to the standard basis
Bn-i = {Ji : 1 < i < n — 1} for Wfu-i, the Petrie matrix Mo-,n-i represents ipa- on VFim-i in the

n-1

sense that, for every integer 1 < i < n — 1, (pa{Ji) = X] ^ij^i- ■'■^ particular, for every element

n— 1 n— 1 n— 1 n— 1 n— 1 n— 1

TiJi in PVirn-i, we have v^^d] "^iJi) = Y.i.Yl riaij)Jj = Yl (^jJj^ where Cj = Yl fi^^ij- Or,

i=l i=l j=l 1=1 j=l i=l

equivalently, in vector form with respect to the standard basis -Bn-i = {Ji '■ 1 < i < n — 1}, we
have (ci, Cs, ■ ■ ■ , c„_i) = (ri, rg, ■ ■ ■ , r„-i) ■ M^,„_i.

Figure 1: The cyclic permutation aj.

One may ask why anybody would like to study strangely-defined matrices such as the Petrie
matrix M^^n-i, especially when conjugate permutations need not have similar corresonding
Petrie matrices so defined (cf. [7]). If we look at the Petrie matrix M^^n-i from the algebraic
point of view, it seems that we have known all interesting things about it |2], 1141 115] . So,
what else is special about it that warrants the further study? This answer comes from the
dynamical systems point of view. Although the definition of M^^n-i may seem opaque, its
study Ill|4l[5l[9l[lh[nilI2l[13l[I7l[l8l[T9l[20^ quite common in the theory of discrete
dynamical systems on the interval : If we define the linearization of a on P„ to be the continuous
map fcr from [l,n] into itself such that /o-(fc) = cr(/c) for all integers 1 < k <n and is linear
on Ji for all integers 1 < i < n — 1 and take Jj's as the vertices of a directed graph and
draw an arrow from the vertex Jj to the vertex Jj if fcr{Ji) 3 Jj, then Mo-,n-i will be the
adjacency matrix [3, p. 17] of the resulting directed graph. For example, if cry denotes the cyclic
permutation 1^6— >5— s>7— >2— ^>3-^4— >-lonP7 (see Figure 1), then the adjacency

2

matrix M^^^q of the corresponding directed graph is given as

1 1 1 0\
10
10
1111
11
110 0/

whose characteristic polynomial is — — + bx^ — — x + 1. You may have noticed
that the coefficients of the characteristic polynomial of M^^^e are all odd numbers. This is
no coincidence. It has been shown in |10| that if a is a cyclic permutation on P„ then the
coefficients of the characteristic polynomial of the adjacency matrix Mo-,„_i of the directed
graph of fa are all odd numbers and hence nonzero.

This adjacency matrix M^^n-i turns out to contain many information on the dynamical
properties of the map fa such as its topological entropy |T], |4j and Artin-Mazur zeta function
[3j which are topological invariants. In [8|, [9], when we study the Artin-Mazur zeta function of
fa for some cyclic permutation a, we are surprised to see that, for some cyclic permutations a
and p, although fa and fp are not topologically conjugate, they still have the same Artin-Mazur
zeta function. Further study reveals that it is because the adajcency matrices of their respective
directed graphs are similar. When we re-examined Theorem 2 of [S] a few years ago, we found
something interesting hidden behind the theorem (cf. Theorem 7 below). This initiates the
investigation of the one-sided and two-sided similarities and weak similarities of permutations.
Our results on permutations may be complementary from the perspective of discrete dynamical
systems on the interval to the book Combinatorics on Permutations by M. Bona [6] .

For convenience, in the sequel, for any set Vm = {f i, V2,--- , fm} of m vectors in PVprn, we

m

shall write f i = X] ^ijJji 1 < < "^i, and call this m x m matrix {bij) the matrix of Vm (with

respect to the standard basis Bm = {Ji '■ I < i < m}) and denote it as MiVmlBm)- For
any finitely many vectors Wi,W2, ■ ■ ■ ,Wk in Wf^, we shall let < Wi,W2, ■ ■ ■ ,Wk > denote the
subspace spanned by Wi,W2, ■ ■ ■ ,Wk- In Theorem 6, we shall let F denote the field Z2 = {0,1}
of two elements and in other cases, we shall let F denote the field M of real numbers.

1

1

1

1

1

2 Definitions of one-sided and two-sided similarities and
weak similarities of permutations

Let n > 3 be a fixed integer and let cr„ be a permutation on P„. In section 1, we associate to
each an an (n — 1) x (n — 1) matrix Ma,^^n-i called the Petrie matrix of o"„. It is clear that we
can define an equivalence relation on the symmetric group Sn of permutations on P„ by simply
using the matrix similarity of Mo-„^„_i's. However, based on Theorems 5 & 7 below, we take a
different approach.

3

In this section, we shall present definitions of one-sided and two-sided similarities or weak
similarities of permutations in Sn and some of their properties. At first look, it may appear
somewhat strange to define these similarities in such peculiar ways. However, they are inspired
by the examples in Theorem 7 below which is motivated by the theory of discrete dynamical
systems on the interval. In the theory of discrete dynamical systems on the interval, a period-
n orbit of a map determines a (cyclic) permutation 7 in Sn which, in turn, determines an
(n — 1) X — 1) zero-one Petrie matrix. By extending the permutation 7 to the right, left,
or, both right and left to a permutation in with m > in a way suggested by Theorem 7
below, we can compare the characteristic polynomials and discuss the matrix similarity of their
corresponding extended Petrie matrices. It is because of this matrix similarity of the associated
Petrie matrices, we call two permutaions in Sn one-sided or two-sided similar. We shall prove
their richness by presenting more examples.

In the sequel, we always let k he a fixed integer which is > 3. Let be a permutation
on Pfc = {1, 2, • • ■ , A; — 1, k}. For any integer n > 1, let ak+n be any permutation on Pk+n =
{1, 2, ■ ■ ■ , k + n — 1, k + n}. We say that Ck+n is a right extension (see Figure 2) of cxfc if

(1) crk+n{i) = CTkii) for all integers 1 < i < k — 1,

(2) (Xk+nit) = <7k{k) < k for some integer t such that k + l<t<k + n,

(3) o"fe+„(j) > k for all integers j ^ t and k < j < k + n.

Figure 2: A right extension of the cyclic permutation (T5.

Remark. Let k and be defined as above. For any integer n > 1, let l3k+i^k+n be any
permutation on the set {k + 1, k + 2, ■ ■ ■ , k + n}. For any integer k + 1 < t < k + n, we
can define a permutation R(crfc, l3k+i,k+n, t) (R- stands for right) on the set {1, 2, 3, ■ ■ ■ ,k + n}
by putting (i) R{ak, Pk+i,k+n,t){i) = crk{i) for all 1 < z < A; - 1; (ii) R{ak, Pk+i,k+n,'t){k) =
Pk+i,k+n{t); (iii) R(o-fc, Pk+i,k+n, = Pk+i,k+nij) toT all k + 1 < j < k + u and j ^ t; and (iv)
R{o'k, Pk+i,k+n,t){t) = (Jk{k). Then it is easy to see that R{ak, Pk+i,k+n,t) is a right extension
of (jfc. Conversely, every right extension of ak can be uniquely obtained this way.

Let ak and pk be any two permutations on Pk and let ak+n and pk+n be any two permutations
on Pk+n which are right extensions of ak and pk respectively. We say that the pair {ak+n, Pk+n) is

4

a synchronized right extension of ak and pk if, for some integer k+1 < j < k+n, au+nU) = ^-kij^)
and pk+n{j) = Pk{k), and ak+nii) = Pk+nif) for o^ll integers i ^ j and k < i < k + n.

For any two integers m > 1 and A; > 3, let and (Xm+k be permutations on and on Pm+fc
respectively. We say that cxm+fc is a left extension (see Figure 3) of cxfc if

(1) (7m+k{rn + i) = m + akii) for all integers 2 < i < k,

(2) crm+fc(s) = m + (Tjfc(l) > m + 1 for some integer s such that 1 < s < m,

(3) cr^+fcO) < m + 1 for all integers j 7^ s and 1 < j < m + 1.

Remarks. (1) For simplicity, we sometimes call Cm+k a left extension of the permutation
0'm+i,m+k{x) = ak{x — TTi) + TTi defined on the set {m + 1, m + 2, m + 3, ■ ■ ■ ,m + k — l,m + k}
which can be seen as a translation of (Xfe to the right by m units.

(2) Let k and ak be defined as above. For any integer m > 1, let am be any permutation
on the set {1, 2, ■ ■ ■ , m}. For any integer 1 < s < m, we can define a permutation L{am, 0"^, s)
(L stands for left) on the set {1, 2, 3, ■ ■ ■ ,m + k} by putting (a) L{am, o"fc, s){i) = am{i) for all
1 < i <m and i ^ s; (b) L(a„, ak, s)(s) = m + (7^(1); (c) L(a„, cxfc, s)(m + 1) = ar„(s); and
(d) L{am, CTk, s){j) = m + ak{j — m) for all m + 2 < j < /c + m. Then it is easy to see that
L(am, CTfc, s) is a left extension of 0"^. Conversely, every left extension of ak can be uniquely
obtained this way.

Figure 3: A left extension of the cyclic permutation a^.

Let (Tfc and pk be any two permutations on Pk and let a^+k and Pm+k be any two permutations
on Pm+k which are left extensions of ak and pk respectively. We say that the pair {am+k, Pm+k)
is a synchronized left extension of ak and pk if, for some integer 1 < j < m, am+kU) = 'fn + cXkiX)
and Pm+kU) = m + Pk{l), and am+k{i) = Pm+k{i) for a// integers i 7^ j and 1 < i < m + 1.

For any integers m > 1, /c > 3, and n > 1, let (Jfc and am+k+n be permutation on Pfc and on
Pm+k+n respectively. We say that am+k+n is a two-sided extension (see Figure 4) of ak if

5

(1) (Jm+k+ni^ + i) = m + akii) for all integers 2 < i < A; — 1,

(2) crm+fc+n(s) = m + cr/c(l) for some integer s such that 1 < s < m,

(3) (Jm+k+nif) <m + 1 for all integers i ^ s and 1 < i < m + 1,

(4) crm+fc+n(^) = rn + (Jk{k) for some integer t such that m + /c + l<t<m + A; + n,

(5) (Tm+k+nU) > TTi + k for all integers j ^ t and m + fc<j<m + fc + n.

I' t i 1

hH-H
v/vy

fixed

Figure 4: A two-sided extension of the cyclic permutation a^.

Remark. Let k and cjfc be defined as above. For any integers m > 1 and n > 1, let and
Pm+k+i,m+k+n be any permutations on Pm and on {m + k + l,m + k + 2,m + k + 3,-- - ,m +
k + n} respectively. For any integers 1 < s < m and m + k + 1 < t < m + k + n, we can
define a permutation T^amyCrk, Pm+k+i,m+k+n, s,t) (T stands for two-sided) on the set Pm+k+n
by putting (a) T(am,o"fc ; l3m+k+l,m+k+ni

s,t){i) = am{i) for all 1 < i < m and i ^ s; (b)
T(am,crfc,/3m+fc+i,m+fc+n, = m + o-fc(l); (c) T{am,crk,f3m+k+i,m+k+n,s,t){m + l) = amis);

(d) T(a^,afc,/5m+fc+i,m+fc+n,s,t)(j) = m + ^^(j - m) for all m + 2 < j < m + A; - 1; (e)

s,t)(m + k) = f3m+k+l (f) T( tm =

m + (Jfc(fc); and (g) T(am, cr^, /?m+fc+i,m+fc+n, s, = /3m+/c+i,m+fc+n(j) for all m + A; + 1 < j <
m + k + n and j 7^ t. Then it is easy to see that T(Q;m, 0"^, /^m+fc+i.m+fc+n, -s, t) is a two-sided
extension of 0"^. Conversely, every two-sided extension of can be uniquely obtained this way.

Let cxfc and pk be any two permutations on P^. and let am+k+n and pm+k+n be any two
permutations on Pm+k+n which are two-sided extensions of Ufc and pk respectively. We say that
the pair {(Tm+k+n, Pm+k+n) is a synchronized two-sided extension of ak and pk if, for some integers
1 < s < m and m+k+l <t< m+k+n, we have am+k+ni-s) = m+akil), Pm+k+n{s) = m+pk{l),
am+k+n{t) = m + ak{k), pm+k+n{t) = m + pk{k), and am+k+n{i) = pm+k+n{i) for all integers
i e [1,771 + 1] U [m + k,m + k + n] \ {s,t}.

We now define right, left and two-sided similarities or weakly similarities of any two per-
mutations on Pfc. Note that these definitions have nothing to do with the conjugation in the
corresponding symmetric group Sk of permutations on P^.

6

Definition 1. Let ak and pk be any two permutations on P^. We say that Ufe and pk (or the
pair {(Tk, Pk)) are right (left, two-sided respectively) similar if, for e?;er?/ synchronized right (left,
two-sided respectively) extension {a, p) of ak and pk, the Petrie matrices of a and p are similar.

Definition 2. Let ak and pk be any two permutations on Pk- We say that ak and pk (or the
pair {ak, Pk)) are right (left, two-sided respectively) weakly similar if, for every synchronized
right (left, two-sided respectively) extension {a, p) of ak and pk, the Petrie matrices of a and p
have the same characteristic polynomial.

Remarks. (1) It is easy to see that right (left or two-sided respectively) similarity defines an
equivalence relation on the set of permutations on Pk (or, on the symmetric group Sk)-

(2) It is easy to see that right (left or two-sided respectively) weakly similarity defines an
equivalence relation on the set of permutations on Pk (or, on the symmetric group Sk).

(3) There are permutations on Pk, for any k > 4, which are right (left, or two-sided respec-
tively) weakly similar but not similar. For example, if ak = (34) and pk = (12) (34), then ak
and Pk are right weakly similar but not right similar. That they are right weakly similar can
be seen by expanding the determinants det[Mf^^^^ k+n—i ~ ^■^) and det[Mpi_^^ k+n—i ~ ^■^) along
the first row using Laplace's formula, where / is the {k + n — l)x{k + n — l) identity matrix and
(ak+n, Pk+n) iS) for any n > 1, any synchronized right extension of ak and pk on Pk+n- However,
for each k > i, ak and pk are not right similar. More examples can be found in section 5.

In this paper, we shall concentrate only on one-sided or two-sided similarity. The following
results which can be verified easily demonstrate how to obtain more examples of one-sided or
two-sided similar permutations from the known ones.

Theorem 1. Let ak and pk be any two permutations on Pk which are two-sided similar. Then
the following hold:

(1) For every synchronized two-sided extension {a, p) of ak and pk, a and p are right, left,
and two-sided similar.

(2) For every synchronized right (left respectively) extension {a,p) of ak and pk, a and p are
left and two-sided (right and two-sided respectively) similar.

Theorem 2. Let ak and pk be any two permutations on Pk which are right (left respectively)
similar. Then, for every synchronized right (left respectively) extension {a,p) of ak and pk, a
and p are right (left respectively) similar.

For any permutation 9k on Pk, we let 61 denote the dual permutation of 6k on Pk such that
6l{i) = k -\- 1 — 6k{k — i), 1 < i < k. It is easy to see that the dynamics of 6k and 6^ on Pk
are mirror symmetric.

Theorem 3. Let ak and pk be any two permutations on Pk which are right (left, two-sided
respectively) similar. Then a^ and pi are left (right, two-sided respectively) similar.

7

We can also combine two pairs of permutations with various similarity properties to obtain
more examples.

Theorem 4. Let i > 4 and k > i + 1 be integers. Let ai and pe be permutations on Pi
such that ai{€) = i — 1 and ae{i — 1) < i — 1. Let ^ and rj be permutations on the set
{£-l,i,i+l,i + 2,--- ,k-l,k} such that ^{i) = i-l, and r]{i - 1) = i and r]{i) > i. Let
{cr^)k, {<yi])k, o-nd {pr])k be the permutations on Pk defined by

{(^V)kix)

and

(cTeix),

ifl<x<i— 1 and cXi

, ifl<x<i— 1 and

[x) =

if £<x<k,

fcTiix),

if I < X < i - 1,

\r]{x),

if i <x <k,

(pi{x),

if I < X < i - 1,

\ Vix),

if i < X < k and ri(x) ^ £

-1,

if i < X < k and ri{x) = i

-1,

ipV)kix)

Then (o"^)fc is a left extension of C, and {prj)k is a right extension of pi and the following hold:

(a) If (J I and pi are right similar and C, and rj are two-sided similar, then {(jC,)k (^nd {(Jri)k are
right and two-sided similar and {(Tri)k and {pri)k are right similar.

(b) If ae and pe are two-sided similar and ^ and rj are two-sided similar, then {(J^)k and (crr/)^
are right and two-sided similar and {o'ri)k and {pT])k are left and two-sided similar.

(^)

1 2 3 4 5 6 7 k-1 k

\J\J/\I\J\J v/v/

\iA^t^/^

2 3 4 5 6 7

Figure 5: The cyclic permutations (o"^)^ and {pr])k-

Remark. Later on, we will see that, for any m > 6, the cyclic permutations ^ : 4 — > m — >
m — 1— >m — 2— >----^6^5— s>4 and ?7:4-^5— s>6^---— s>m — l-^m^4 are

8

two-sided similar (Theorem 8) and the cychc permutations cts:!— >3— >2— >5— >4— >1 and
Ps:!— >5— >2— >3— >4— >1 are right similar (Theorem 12). Therefore, by Theorem 4(a), for

any k > 6, the cyclic pcrnnitations (o"^)^ :1— >3-^2^A;^A'; — 1— — 2^---^7— >6— >
5 ^ 4 ^ 1 and {pr])k :1^5^6^7^----^A;-1^A;^2^3^4^1 (see Figure
5) are right similar. However, it can be easily checked that they are neither left nor two-sided
similar (cf. Theorem 12).

Proof. The desired results follow easily from the observations that the pair ((o"^)^, {(yrf)).)) is
a synchronized left extension of ^ and r] and the pair {{(Jr))k, {pv)k) is a synchronized right
extension of and pe. ■

Although two permutations with similar corresponding Petrie matrices need not be right,
left, or two-sided, similar or weakly similar, we can still obtain more examples by "expanding"
them to "longer" permutations.

Theorem 5. Let m > 0,n > and k > 3 be integers with m + n > 1. Let and pk be
permutations on and let (Tm+k+n o-i^d Pm+k+n be permutations on Pm+k+n such that

(1) If m = 0, then (Jk+nif) = (^kif) and pk+n{i) = Pk{i) for all integers 1 < i < k and
(^k+n{j) = Pk+n{j) {>k+l) for all integers k + l<j<k + n,

(2) If n = 0, then (Tm+k{j) = Pm+k{j) (< m) for all integers 1 < j < m and (Xm+kU) =
m + ak{j — m) and pm+k{j) = ^ + Pk{j — ^) for all integers m + l<j<m + k,

(3) If m > 1 and n > 1, then (Tm+k+nii) = Pm+k+n{i) < ""^ for all integers 1 < i < m, and
(^m+k+n{j) =m + ak{j - m) and Pm+k+nU) =m + pk{j - m) for all integers m + l <j <
m + k and am+k+n{x) = Pm+k+n{x) > m + k + 1 for all integers m + k + 1 < x < m + k + n.

Assume that the Petrie matrices of ak and pk are similar. Then the following hold:

(1) // both ak and pk fix at least one same endpoint of [1, k], then the following hold:

(a) If ak{k) ~ k — pk{k), then (Tk and pk are right similar.

(b) //(7fe(l) — 1 — Pfc(l); then and pk are left similar.

(c) If (7k{k) — k — Pk{k) and (7^(1) = 1 = Pfe(l); then ak and pk are two-sided similar.

(2) // both ak and pk fix no same endpoint of [1, k], then the Petrie matrices of am+k+n o,nd
Pm+k+n have the same characteristic polynomial and the following also hold:

(a) If m = 0, then ak+n CLnd pk+n are right weakly similar. Furthermore, if 1 is not an
eigenvalue of the Petrie matrix of p^, then the Petrie matrices of ak+n and pk+n are
similar and, a^^n and Pk+n are right similar.

(b) If n = 0, then am+k and Pm+k are left weakly similar. Furthermore, if 1 is not an
eigenvalue of the Petrie matrix of pk, then the Petrie matrices of am+k and Pm+k are
similar and, am+k and Pm+k are left similar.

9

(c) If m > 1 and n > 1, then (Jm+k+n o-nd pm+k+n right, left, and two-sided weakly
similar. Furthermore, if 1 is not an eigenvalue of the Petrie matrix of p^, then
the Petrie matrices of am+k+n and pm+k+n are similar and, am+k+n and pm+k+n are
right, left, and two-sided similar.

Remark. In the above theorem, if 1 is an eigenvalue, then the result need not hold. For
example, let a = (13) and p = (13)(24). When considered as permutations on P4, the Petrie
matrix of a with respect to the basis {Ji, J2, J3} is the same as that of p with respect to the
basis { Ji, J3, Ji + J2 + ^3}- So, the 3x3 Petrie matrices of a and p are similar and since
^ct{Ji + J2) = Ji + J2, 1 is an eigenvalue. However, the Petrie matrices of the permutations
(13) (56) and (13) (24) (56) are not similar because they have distinct minimal polynomials.
Therefore, the permutations (13) and (13) (24), when considered as permutations on P5, are not
right similar although they are right weakly similar. Their respective Petrie matrices are not
similar either because they satisfy distinct minimal polynomials.

Proof. Suppose m = 0. Since the Petrie matrices of ak and pk are similar, there is a basis
L = {Li, L2, ■ ■ ■ , Lk-i}, where the Lj's are linear combinations of Ji, J2, ■ ' ' y Jk-i for W^k-i
such that if g is the linear transformation from W^k-i onto itself defined by putting g{Ji) = Li
for all 1 < 2 < A; — 1 then we have {(fp^^ o g){x) = {g o ifak){^) W^k-i. Let Ig denote the
i X i identity matrix. Then by expanding the determinants det(Mo-j.^^ — \Ik+n-i) and
det(Mpj.^^ fc+„_i ~ ^h+n-i) along the {k + 1)^* column using Laplace's formula, we easily obtain
that these two determinants are equal. That is, the Petrie matrices of (Jk+n and Pk+n have the
same characteristic polynomial. Since n > 1 is arbitrary and o"fc+„(= Pk+n) is arbitrary on the
set {A; + l,fc + 2, A; + 3, ■■■ ,k + n — l}, this implies that a^+n and pk+n are right weakly similar.

On the other hand, if 1 is not an eigenvalue of the Petrie matrix of pk, let Idfc_i be the
identity map on W^k-i. Then the linear transformation ipp^ — Idk-i is invertible. Hence, there

fc-l k-l

exists real numbers ai, 02, ■ ■ ■ , a^-i such that {(pp^ — ldk-i){Yl o^iLi) = ^ Lj — ^ Jj. Let

i=l i=(Tk{k) i=Pk{k)

k-l

S = {Si, S2, S3, ■ ■ ■ , Sk+n-i} = {Li, L2, L3, ■ ■ ■ , Lk-1, ^ aiLi + Jk, Jk+i, Jk+2, ■ ■ , Jk+n-i] (in

i=l

that order). Then it is clear that S* is a basis for W^k+n-\. Let h be the linear transformation
from W^k+n-i onto itself defined by putting h{Ji) = Si for alll<i<A; + ri — 1. Then we have
if Pk+n °h){x) = {ho {p^^^^){^x) on W^k+n-i. Therefore, the Petrie matrices of ak+n and pk+n are
similar. Consequently, since any synchronized right extension of (Jk+n and pk+n are just another
different ak+n and pk+n, and so their respective Petrie matrices are similar. This implies that
(Tk+n and pk+n are right similar. This confirms (2a). (2b) and (2c) can be proved similarly. ■

3 Examples of permutations which are right, left or two-
sided, similar or weakly similar

The following result is taken from |j4], I15| .

10

Theorem 6. Let n > 3 be a fixed integer. Let Z2 = {0, 1} denote the field of two elements.
Let a and p be any two maps from Pn into itself such that neither a nor p nor p o a assumes
the same value at any two consecutive integers l<i<i + l<n. Then we have ippoa = V^p o V^o-
on Wj^^Ti,-!. In particular, if a is a permutation on Pn, then ^pcr is an isomorphism on W^-n,-i
and the Petrie matrix of a has determinant ±1.

Proof. For any two distinct real numbers a and 6, let [a : h] denote the interval [a, h] if
a < 6 or the interval [6, a] if a > h. Since the vector space W^^n-i is over the field Z2 of
two elements, for any map 7 on P^ with '-){%) 7^ 7(2 + 1) for aX\ 1 < i < n — 1 and any
two integers 1 < A; < £ < n, we easily obtain that (y9^([A;,£]) = Yy{k) : 7(£)]. Therefore,
ipp{(fa{Ji)) = fpiWii) ■ cr{i + 1)]) = [p{cr{i)) : p{a{i + 1))] = (p o a){Ji). This shows that

^poa = ^pO^a on VT^^n-l. ■

Figure 6: The permutations a and p in Theorem 7.
We now come to the main result which initiates all of these (cf. [8, Theorem 2]).
Theorem 7. Let m > 1 and n > be integers. Let a be a permutation on Pm+n+4 such that

(1) (T{m + 2) =m + 3,

(2) a{m + 3) = m + A,

(3) a{s) = m + 2 for some integer s such that 1 < s < m,

(4) a{i) < m for all integers i ^ s and 1 < i < m + 1,

(5) a{j) > m + 5 for all integers j ^ t and m + 4 < j < m + 4 + n if n > 1,

(6) cr(t) = m + 1 for some integer t such that m + 5<t<m + A + nifn>l,

(7) cr(m + 4) = m + 1 ifn = 0.

We also let p be a permutation on Pm+n+i such that

11

(1) p(m + 2) =m + l,

(2) p{m + 3) = m + 4,

(3) p{s) = m + 3,

(4) p{t) =m + 2 ifn>l,

(5) p(m + 4)=m + 2 ifn^O,

(6) p{i) — a{i) elsewhere.

Then the Petrie matrices of the permutations a and p are similar.

Remark. Note that our assumption imphes that a and p have exactly the same action (and
hence are indistinguishable) on the set {i : 1 < i < m + 1, i ^ s} and, if n > 1, also on the set
{j: m-\-A<j<m-\-n-\-A, j^t}. This motivates our definitions in section 2 of right, left
and two-sided similarities of permutations on a finite set.

Proof. Recall that, for every permutation A on the set {1, 2, • • • , m + n + 1, m + n + 2, m +
n + 3, m + n + 4}, the linearization fx of A on the interval [1, m + n + 4] determines a linear
transformation on W-^m+n+s such that, for real numbers a^'s,

(m+n+3 X m+n+3 ii ii

aiJA = ai(px{Ji), where (pxiJi)^^Jj if fxiJi) ^ [J Jj-

1=1 ' i=l j=ki j=ki

WC now show that the set = { Ji, J2, ■ ■ ■ , Jm, Jm+l + Jm+2, Jm+3, '^pi.Jm+z), Vpi.Jm+i),

(Pp{Jm+5), ■ ■ ■ ) '^pi'Jm+n+s) } forms a basis for W^m+n+s. For n > 0, let uj be the permutation on
Pm+n+4: defined by putting a;(i) = i for all integers 1 < i < m, u!{m+l) = m+3, and = p{j)
for all integers m+2 < j < m+n+A. Then (puj{Ji) = Ji for all integers 1 < i < m — 1, (pu,{Jm) —

Jm + <^^+l + <^m+2, ^ixi{,Jm+\) — -^m+l + <^m+2, V'a; ( <-'m+2 ) = <-^m+l + <^^+2 + <^^+3, ^nd </?a,(Jj)

./ for all integers m + 3 < j < m + n + 3. It is easy to see that the set S is equal to the

set T = { V?(^(Jl), ^^{J-l), ■■■ , <foj{Jm-l), <^uj{Jm) - Vio{Jm+l)- '^AJ,n+l)^ ^ UJ {Jm+2) ^ ^^{Jm+l)-,

vUJm+3), ^uj{Jm+i)-, vUJrn+5), - ■ ■ , 'fc^iJm+n+s)}- Therefore, by elementary operations, the
determinant of the matrix M{T \ {Ji, J2, J3, ■ ■ ■ , J^+n+s}) equals that of the matrix M{{ip^{Ji) :
l<i<m-|-n-|-3}| { Ji, J2, • • • , Jm+n+3}) which is, by Theorem 6, ±1. Consequently, the
determinant of the matrix M{S \ { Ji, J2, J3, • • • , Jm+n+s}) equals ±1. This shows that S is a
basis for W^m+n+s.

Let h be the linear isomorphism from W^m+n+s onto itself defined by

' h{Ji) = Ji, 1 < i < m,

^ h{Jrn+l + Jm+2) — Jm+l,
h{Jm+3) = Jm+2,

^ h{ipp{Ji)) = Ji, m + 3<i<m + n + 3.

12

We now show that {hoipp){L) = (y^o- o /?,) (L) for every L G S*. We have six cases to consider:

Case 1. For some integers 1 < i < m and 1 < ki < m, ifp{Ji) = [ki,m + 3] (since
p{s) =771 + 3, this means that i = s — 1 or s). In this case, we have h{(pp{Ji)) = h{[ki,7n + 3]) =

h{[ki,m+l] + Jm+l + Jra+2) = h{[ki, 711 + 1]) + h{Jm+l + Jra+2) = [ki, 771 + 1] + Jm+1 = [h, 771 + 2] =

iPa{Ji) = <^cT{h{Ji)). Thus, {h o ipp){Ji) = {(fa o h){Ji).

Case 2. 1 < i < m and m + 3 ^ ipp{Ji). In this case, we have fp{Ji) C [l,m + 1]. So,
h{ipp{Ji)) = (pp{Ji) = (Pa{Ji) = (Pa{h{Ji)). Thus, {h o (Pp){Ji) = {ipa o h){Ji).

Case 3. L = Jm+i + Jm+2- In this case, we have h{(pp{J.m+i + Jm+2) = h{(pp{Jm+i) +

Vp{Jm+2)) = h{[p{7n + l),m + 1] + J„+i + Jra+2 + Jm+s) = h{[p{7n + l),m + 1]) + h{Jra+l +

Jm+2) + HJrn+s) = [pirn + 1), m + 1] + J^+i + Jm+2 = [pim + 1), m + 3] = [a{7n + 1), m + 3] =

^a{Jm+l) = (Pa{h{Jm+l + Jm+2))- ThuS, {h O ipp){Jm+l + Jm+2) = {^a ° h){Jm+l + Jm+2) ■

Case 4. L = Jm+s- In this case, we have {hoipp){Jm+z) = h{ipp{Jm+z)) = Jm+'i (by definition

of h) = iPa{Jm+2) = ^a{h{Jm+3)) = {^a ° h){Jm+3)-

Case 5. L = fp{Ji) = [m + 2, ii] for some integers m + 4<-j<m + n + 3 and m + 4 <
ii < 771 + 71 + A (since p{t) = m + 2, this means that i = t ot t — 1). In this case, we have
h{ipp{L)) = h{ipp{Lpp{Ji))) = h{Lpp{[7n + 2, = h{ipp{Jm+2 + Jm+i, + [m + 4, ii])) = h{Jm+i +

Jm+2 + Jm+3 + Vp{Jm+3)+Vpi[fn + 4:,ii])) = h{Jm+l + Jm+2) +h{Jm+z) + h{'P piJm+z)) + h{(p p{[m +

4, = Jm+1 + Jm+2 + Jm+i, + [m + 4, ii] = [m + 1, ii] = ip„{Ji) = ip„{h{ipp{Ji))) = Lp„{h{L)).
Thus, {ho^p){L) = {if,oh){L).

Case 6. L = fp{Ji) for some integer m + 4 < i < 7n + 7i + 3 and m + 2 ^ L. In
this case, ^p{J'i) C [m + 4, m + n + 4]. So, (fp^L) = Lpp{Lpp{Ji)) C ^pi[7n + 4, m + n + 4]).
Thus, h{ifp{L)) = h{ipp{ipp{Ji))) = iPp{Ji) = iPa{Ji) = ^Pa{h{^PpiJi))) = ipa{h{L)). Hence,
{ho^^){L) = {^^oh){L).

Therefore, we have shown that {hoipp)[L) = {iprjoh){L) for every L E S. Thus, hoi^p = ipfjoh
on W^m+7i+3. Since h is an isomorphism from W^m+u+a onto itself, this implies that (pp is
conjugate to through h. Hence the Petrie matrix of a is similar [16j to that of p. ■

The following result is an easy consequence of Theorem 7.

Theorem 8. Let k > A, and 3 < 7i < k — 1 be integers. Let an,k be the cyclic permutation from
Pk onto itself such that

n,

i + 1 for all n < i < k — 1,

71 — 1

j — 1 for all 2 < j < 71 — 1.

(1) a„,fc(l) =

(2) a-„,fc(i) =

(3) (Tn,k{k) =

(4) ar.kij) =

13

Furthermore, let a2,k denote the cyclic permutation on Pk such that o'2,k{i) = i + 1 for all
1 < i < k — 1 and (Ti,k{k) — 1; and let (7k,k denote the cyclic permutation on Pk such that
Cfe,ifc(l) = k and (Tk,k{j) — j ~ ^ for all 2 < j < k. Then the following hold:

(1) If k > 5, then all (Jn,k, 3 < n < k — 1, are right, left, and two-sided similar to one another.
Moreover, the Petrie matrices of Cn^k, 3 < n < A; — 1, are similar to one another.

(2) If k > 4 and n is any integer with 3 < n < k — 1, then (T2,fe and cr„ ^ are left and two-sided,
but not right, similar. Moreover, the Petrie matrices of a2,k and an,k are not similar
because they have distinct traces.

(3) If k > 4 and n is any integer with 3 < n < k — 1, then cjn^k and ak^k are right and
two-sided, hut not left, similar. Moreover, the Petrie matrices of a^^k and ak,k are not
similar because they have distinct traces.

(4) If k > 4, then a2,k and ak,k are two-sided, hut neither right nor left, similar. Moreover,
the Petrie matrices of a2,k and (Tk,k are similar.

Remark. It follows from (4) of the above result that, for any two (cychc) permutations on P^,
even their respective Petrie matrices are similar, there is no guarantee that they are one-sided
(right or left) similar. They need not be two-sided similar either, see examples in Theorem 12
below.

Proof. For each integer 3 < i < n — 2, the Petrie matrices of ai^k ^-nd CTj+i^fc are similar
by Theorem 7. So, the Petrie matrices of (Tn,^, 3 < n < A; — 1, are similar to one another.
Furthermore, it follows from Theorem 6 that, for each integer 2 < i < k — 2, the cyclic
permutations ai^k ^-nd CTj+i^fc are left and two-sided similar. Therefore, all cr^^fc, 2 < n < A; — 1,
are left and two-sided similar to one another. Similarly, by Theorem 7, all (T^^fe, 3 <n <k, are
right and two-sided similar to one another. In particular, all (Tn,k, 3 < n < k — 1, are right, left
and two-sided similar to one another.

On the other hand, by direct computations, for any integers k > n > 3, the trace of the
Petrie matrix of the cyclic permutation 1^2— >3— — 1— >A;-|-1— >lisl while
the trace of the Petrie matrix of the cyclic permutation l^n^n+l^---^k — 1^
/c— s>A; + l^n— l^n — 2^---^3— s>2— s>lis3. So, for any 3 < n < A; — 1, the
Petrie matrices of the cyclic permutations 1^2^3^---^k — l^k^k + 1^1 and
l—>n—>n-|-l— — l—>A;—>A;-|-l—>n — l—>n — 2— >---—>3—>2—>l are not
similar. Therefore, for any 3 < n < /c — 1, the cyclic permutations a2^k and (T„ ^ are not right
similar and the Petrie matrices of o"2,fc and an^k are not similar. Similarly, for any 3 < n < A; — 1,
the cyclic permutations ak,k and an,k are not left similar and the Petrie matrices of ak,k and
an,k are not similar. ■

We shall need the following result.

Lemma 9. Let A; > 3 and n > 3 be fixed integers and let /i be any permutation on Pk+n
such that = i — 1 for all integers 2 < i < A; — 1 and /x(l) = k < ii{k). Then the set

14

^ = I E^[fc,M^)], ■■■ ,^i-\%Km, v^-Vk),

L i=i

(^J~^(Jfc+i), (^J;-2(Jfc+2), ■ ■ ■ , <^J;"2(Jfc+„_i)| equals the set { V^^'^{J^) : 1 < i < k + n - 1} and

so is a basis for PVRfe+n-i. Furthermore, the determinant of M{S\Bn+k-i) is ±1, where Bn+k-i
is the standard basis for W^n+k-i.

k-l

Proof. By direct computations, we obtain that Ji = V5^~^( 7^-2), and, since [/c,/x(/c)] =

=1

(f'^ "^{Jk-s) — 2(y9|^ ^{Jk-2), we have, for every integer < i < k — 4,
and

k-l k-l
i=2 i=2

Therefore, ^ = { ^TVk-s) - 2^^-\J,^2). ^TVk^^) - 2cp'^^-\Jk-s) , v'-^Jk-,)

- 2^j-2(j,_4), - 2v\r%h), E^TVr) - ^TVi), vl-%h). vl"\.h+i).

i=2

ip'^~^ {Jk+2) , ■ ■ ■ , V^^'^i.Jk+n-i) }• By applying elementary operations to the set S, we obtain
the set T = { (p^~'^{Ji) : 1 < i < k + n — 1}. By Theorem 6, the determinant of M{T\Bn+k-i)
equals (±1)'^"^. Therefore, the determinant of M{S\Bn+k-i) equals ±1. Consequently, S is
also a basis for W-ok+n-i. ■

^ h+H

u V i-1 j j+1 k-l k

j-1 J J+1 ^-y}

U V

s

Figure 7: The permutations ak and pk in Theorem 10.
The following result is similar to Theorem 4 in some sense.
Theorem 10. Let k > j > 3 be integers and let ak and pk be two permutations on Pk such that

(a) There exists an integer 1 < s < j — 2 such that crk{s) = j and Pk{s) = k;

(b) crfe(x) = pk{x) < J — 1 for all integers 1 < x < j — 1 and x 7^ s;

15

(c) ak{x) = X + 1 for all integers j < x < k — 1;

(d) Pk{x) = X — 1 for all integers j + 1 < x < k;

(e) (Tk{j - 1) = Pk{j - 1) < c^fc(^) = Pk{j) < j - 1-

Then ak and pk are right and two-sided, but not left, similar. Moreover, the Petrie matrices
of (7fe and pk are not similar because they have distinct traces.

Reiiicirks. (1) Note that ak and pk involve the following three permutations : The cyclic
permutations ak-j+i :l—>2—>3— >•••—>/;; — — j + and (^k-j+i '■ 1— — j' + l— >

fc — J— >3— s>2^1, and the permutation tTj, where = Ckii) for all 1 < i < j — 1
and ■nkU) = <^k{k). Here, (Tk is a right extension of nj and pk is a left extension of Pk-j+i and,
by Theorem 8(4), ak-j+i and Pk-j+i are two-sided similar.

(2) If ak{k) = pk{j) < ak{j - 1) = Pk{j - 1) < j - 1, then ak and pk need not be right or
two-sided similar. For example, if j = 4 and A; > 5 and

(7fc:1^3^2^4^5^6^ > k-1^ k^l

and

Pk:l^3^2^k^k-l^k-2^k-3^ ^6^5^4^1,

then the Petrie matrices of the synchronized right extensions

1^3^2^4^5^6^ >k-l^k^k + l^l

and

1^3^2^A;^A; + l^A;-l^A;-2^A;-3^ >6^5^4^1

have distinct determinants (— l)'^^^, (— 1)*^ respectively. So, ak and pk are not right similar.
Similarly, the Petrie matrices of the synchronized two-sided extensions :

1^4^3^5^6^7^ ^A;-1^A;^A; + 1^A; + 2^2^1

and

1^4^3^A; + l^A; + 2^A;^A;-l^A;-2^ ^7^6^5^2^1

have distinct determinants (— 1)*^, (—1)'^'^^ respectively. So, ak and pk are not two-sided similar.

Proof. For any positive integer n, let {ak+n, Pk+n) be a synchronized right extension of ak and pk-
Let ^ak+n and Pa^+r, be the linear transformations on W^k+n-i determined by the linearizations

k-l

of ak-\-n and Pk^n respectively as introduced in section 1. Let 5* = { Ji, J2, • • • , Jj-2-i Ji-i

i=j-l

[k,pk+n{k)]. (ff,^^^{[k,pk+n{k)]), ipl^^J[k,pk+n{k)]), ^l^^J[k,pk+n(k)],---, ip';;i-\[k, Pk+n(k)],

'fpk+n^'^k), (Pp;f^{Jk+i), ■ ■ • , V^pfe;i(-^fc+n-i) }• Let ^ be the permutation on the set {j +
l,j-\-2,--- , k + n — 1, k + n} such that p{i) = i — 1 for all j <i < k — 1, p{j — l) = k, and p{i) ~

16

k-l

Pk+n{i) for all k < i < k+n. By Lemma 9, the set T = { Yl Ji, [^^ Pk+n{k)], ipp^_^^{[k, pk+n{k)]),

i=j-l

V>l,+„{[k,Pk+n{k)]), ■ ■ ■ ,(^^-^-i([fc,pfe+„(fc)], ^XLW^ v)>~iSJk+i). ■ ■ ■ .<^p;+„(^fe+"-i) } equals
the set {^^fj^-' {Ji) : i — 1 < i < k + n — \}. So, by Theorem 6 and [16| . T is a basis and so, S
is a basis for W

Let h be the hnear isomorphism from W^k+n-i onto itself defined by
'h{Ji) = Ji, for 1 < i < j - 1,

k-l

KJj-i) = E Ji^

i=j-l

KJj+i) = ^'pk+S\^^Pk+n{k)]), 0<i<k-j-l,
[h{J,) = ip''^;l{J,), k<t<k + n-l.

Then it is easy to see that {h o ipak+„){Ji) = ivpk+n ° for all 1 < z < A; + n — 1. Therefore,

the Petrie matrix of ak+n is similar to that of pk+n- This shows that ak and pk are right similar
and, consequently, the two-sided similarity of ak and pk also follows.

Let (Tfc and pk denote the cyclic permutations 1— s>4— s>5^6^---— — l^fc— s>2^
3 — i> 1 and — l—>-/c — 2— s>---^5—>4—>2^3—s>l respectively. The Petrie

matrices of the cyclic permutations 1^5^6^7^---^A;— 1— s>/c— s>/c + l— >-3— i>4— >■
2 — i> 1 and 1— s>A; + l^/c— i>/c — l-^---— >6^5^3— >4— >2— i>l have distinct traces.
Therefore, ak and pk are not left similar. ■

The above result presents a method to construct permutations on Pk with k > 5 which are
right and two-sided similar. This, combined with Theorem 4, will produce even more examples
which are right and two-sided similar. In the following, we introduce some concrete examples
by applying Theorem 4 to Theorems 8(4) and 10.

Figure 8: The permutations ak, pk and pk in Corollary 11.

Corollary 11. Let j > 3 be an integer and let tcj be any fixed permutation on Pj such that
■Kj{i — 1) < 7ij{j) < j . For any integer k > j + 2, let ak, Pk, Pk, md Vk be the permutations on

17

Pk defined by

ak{x)

Pk{x)

<

Uj{x),
x + 1,

'nj{x),

J + l,
x + 1,

ifl<x<j-l,
if j < X < k - 1,
if X — k,

if 1 < X < j and ttj (x) ^ j,
if I < X < j and nj {x) = j,
if j < X < k — 1,
if X = k,

if l<x <j, and 7ij{x) ^ j,
if 1 < X < j, and Trj{x) — j,
if j <x <k,

and

if I < X < j - 1,

Uk{x)

X

if j + '2 < X < k,
if x = j + 1.

Then a^, Pk and jik are right and two-sided similar to one another, and pk are also left
similar while pk and pk need not be, and the Petrie matrices of and pk are similar (because
(7j+i and pj+i are right similar by Theorem 10) while those of pk and pk are not because they
have distinct traces. Furthermore, Uk is neither right nor two-sided similar to any of Uk, Pk,
and Pk-

Remcirks. (1) Note that Uk is a right extension of the permutation tTj, pk is a left extension
of the cychc permutation j'— + j' + 2— — l—>A;—>j', //^ is a left extension of
the cyclic permutation j— — 1— — 2^---^j + 2— + and Vk is another

right extension of vr^ which is different from (jfc. The above result says that, among these four
various extensions, three are right and two-sided similar to one another while the remaining
one is neither right nor two-sided similar to any of the three.

(2) In the above corollary, if wc take j = 5 and the permutation ttsiI— >3— >2— >5—
4^1, then the corollary says that a^, and C,k (see Figure 9), for any k > 7, are all right
and two-sided similar to one another. Also, by Theorem 10, ae and Ae are right and two-sided
similar. As for left similarity, it follows from Theorem 7 that ak and Afc are left similar for all
k > 7 while and Xq are not left similar because of distinct traces for some easy synchronized
left extensions. Moreover, for each k > 7, (k is neither left similar to ak nor to A^ because of
distinct traces for some easy synchronized left extensions.

(3) In the above corollary, if we take j = 5 and the permutation 7r5:1^5^2—

4 — >■ 1, then the corollary says that 7^, 6k and ^^^(see Figure 10), for any k > 7, are all right
and two-sided similar to one another. On the other hand, by Theorem 10, 76 and 6q arc (right
and) two-sided similar, and so, for any k > 7, jk and 6k are also left similar. But, and 6q

18

Figure 9: The permutations a^, and (k in Remark(2) following Corollary 11.

Figure 10: The permutations 7^, 6k and 6k in Remark(3) following Corollary 11.

are not left similar because of the distinct traces of some easy synchronized left extensions.
Furthermore, for any k >7, 6k cannot be left similar to any of 7^ and Sk because of the distinct
traces of some easy synchronized left extensions.

Proof. By Theorem 10, Cj^i and p^+i are right and two-sided similar. On the other hand, for
k > j + 2, {(Tk, Pk) is a synchronized right extension of (Xj+i and Pj+i. This, combined with
Theorem 2, implies that ak and pk are right, left, and two-sided similar. On the other hand,
by Theorem 8(4), the cyclic permutations ak-j+i '■ 1— '•2— *3— ^---^A; — j + l— >1 and
Pk-j+i :l— *k — j + l-^k — j^k — j — 1^---^3^2^1 on Pk-j+i are two-sided
similar. Since {pk,Pk) is a synchronized left extension of ak-j+i and jSk-j+i, we obtain that pk
and Pk are right and two-sided similar. ■

In the following, we present more examples of cyclic permutations which are right, but
neither left nor two-sided, similar.

19

1 2 3 4 5 6 7 k-1 k

/^/^^tT^iA^ A^

2 3 4 5 6 7

Figure 11: The cyclic permutations at and Ok in Theorem 12.

Theorem 12. Let > 5 be an integer. Then the cyclic permutations

afc:1^3^2^5^6^7^ ^A;-2^A;-l^A;^4^1and

^fc:l^A;^A;-l^A;-2^ ^7^6^5^2^3^4^1

on Pfc are right, but neither left nor two-sided, similar. Moreover, their respective Petrie

matrices are similar if = 5 and not if > 5.

Remark. It follows from the above result that the Petrie matrices of and 9^ are similar.
However, they are not two-sided similar.

Proof. For any integer n > 0, let (ofc+n, Ok+n) be a synchronized right extension of ak and 9k
on Pk+n and let fak+„ and fe^+n be the linear transformations on W^k+n-i determined by the
linearisations of ak+n and 9k+n respectively as introduced in section 1. Let S = { Ji + J2, Ji +

k-1

J2+J3, J3-J2, E [k, Ok+n{k)], fe,+Ak, Ok+n{k)]), vl^Slk, 9k+n{k)]), ■ ■ ■ , fe^U^k, 9k+n{k)]),

i=2

fe^+Mk), fe^^JJk+i), (fe;^JJk+2), ■■■ , We want to show that 5 is a basis
for WTg^k+n-i. Let V be the subspace spanned by S. It is easy to see that {Ji, J2, J3} C V.
Furthermore,

k-1 k-1

^dk+SJl) =^Ji- J2 e < Ji,J2,J3,^Ju[k,0k+n{k)]>,

i=2 i=2

k-1

^e^:+„iJ'2) = J3 e < Ji,J2,J3,^Jh[k,dk+nik)]>,

i=2

k-1

^e^^+Ms) = Ji + J2 + J3 e <Ji,J2,J3,^Ji,[k,9k+nik)]>,

i=2

k-1

^ek+SJi) = Ji ^ <Ji,J2,J3,'^Ji,[k,9k+nik)]>,

2=2

20

and

fe-i fc-i fe-i

"POk+AYl '^^) ^ Jl + J3 + {Jl + J2 + J3) + J2 '^* + [^' ^k+n{k)] G < Ji, J2, J3, J] Ji, [/c, ^fe+„(A;)] > .
1=2 i=2 i=2

Therefore, for 1 < i < 4,

k-l

vlulS^i) ^ < -^1' -^2, ^3, 5] -^^^ ^fc+n(A:)], <^e,+„([A:, ^fc+n(A:)]), • • • , f^U^^, ek+n{k)]) > .

i=2

On the other hand, for 2 < i < A; - 5, cp';-^-'{Jk-i) = J5. So, (^^^^'X-^^fc-O = (•^^s) =

k-l

9'0fc+„(<^2 + + </4) e < -^1, -^"2, -^3, E -''i, [fc, 6'fc+n(/c)] >■ Consequently,

i=2

k-l

Ve^+Mk-i) e < -^l' -^2, ^3, 5^ Ji: [K Ok+n{k)l <Pe,+Ak: Ok+n{k)]), • • • , Vl'lJiK Ok+n{k)]) > ■

i=2

Finally, since ipe^+SJk-i) = Jk-2 + Jk-i + [k, 9k+n{k)], ip^Q~^^{Jk-i) = {J2 + ^3 + J^) + (-^5 +

Je + • • ■ + Jfc-i + [k, Ok+n^k)] + V6u+S[k: Ok+n{k)]) + • • • + <^e;+„([^' ^fe+n(^)]))- Therefore, for
5 < i < A; — 1, we have

fc-i

^ < -^1' -^2, >^3, XI ^fc+n(^)], <^e,+„([A;, ^/c+n(A;)]), • • • , <"^'„([fc, ^fe+n(fc)]) > .

i=2

This shows that the set T — Wt^l^iJi) '■ ^ < i < k + n — 1} is contained in V . Since, by
Theorem 6, T is a basis for W^k+n-i, we obtain that V — W^k+n-i. That is, 5" is a basis for

Let h be the linear isomorphism from W^k+n-i onto itself defined by

Ji + J2,

J1 + J2 + J3,

KJ^) =

J3 — J2,

' KJa) =

k-l
i=2

h{J5+i)

= ^l^^^{[k,ek+n{k)]),o<t<k

MJ3) =

ip''e;l{Jj),k<j <k + n-l.

Then it is easy to see that {h o ipak+„){Ji) = iVdk+n ° h){Ji) for every integer l<i<k + n— 1.
Thus, hoip^^_^^ = ipe^^^oh on W^k+v.-i. Since h is an isomorphism from W^k+n-i onto itself, this
implies that ^ak+ri conjugate to v^efe+„ through h. Consequently, the Petrie matrix of Q;fe+„ is
similar to that of ^fe+n- This shows that and 6),. are right similar and (by taking n — Q) the
Petrie matrices of 0:5 and 9^ are similar. On the other hand, for k > 5, the Petrie matrices of
Q!fe and 9k are not similar because they have distinct traces.

21

Let /ifc+2 and denote the cyclic permutations l—>4—i>3^6^7^8— s>A;^

k + l^k + 2^^^2^laiiAl^k + l^k + 2^k-^k-l^k-2 ^7^6^

3— >4^5^2^1on Pk+2 respectively. By using elementary row operations, it is easy to
see that the determinant of the Petrie matrix of iik+2 is (—1)'^^^ while that of i'k+2 is (— l)'^-
Since they are different, this shows that au and 9k are not two-sided similar.

Finally, the Petrie matrices of the cyclic permutations 1^4^3^6^7^8^---^
fc-l^fc-^fc + 1^5^2^1andl->A; + l^A;^A;-l^---7^6^3^4^5^
2-^1 are not similar because they have distinct traces. So, ak and Ok are not left similar. ■

, , , r>,

12 3^

\ 5 i

1

1 2 3 4 5 6 7 H k-1 k

Figure 12: The cyclic permutations (3k and 5k in Theorem 13.

Theorem 13. Let k > 5 be an integer. Then the cyclic permutations

/3fc:1^3^2^4^5^6^7^ ^A;-1^A;^1 and

6k: l^k^k-l^k-2^ >6^5^3^2^4^1

on Pk are right, hut neither left nor two-sided, similar. Moreover, their respective Petrie ma-
trices are not similar because they have distinct traces.

Proof. It is easy to see that the Petrie matrix of (3k is not similar to that of 6k because they
have distinct traces. We now show that (3k and 6k are right similar.

For every positive integer n, let {(3k+n, 6k+n) be a synchronized right extension of (3k and
6k on the set Pk+n- Let and '{>Sk+n be the linear transformations on W^k+n.-\ deter-

mined by the linearizations of (3k+n and 6k+n respectively as introduced in section 1. Let S =

k-l

{Ji,Ji + J2 + Js, E Ji, [k,6k+n{k)], ^5,+A[f^,6k+n{k)]), ^j^^^{[k,6k+n{k)]), ^^s^^^{[k,6k+n{k)]),

■■■,^',;l{[k,6kj{k)]), ^1:tSJk), d:,t('/fc+2), ■■■ ,^1:tSJk+n-i)} ^riA let V be

the vector space spanned by S. We want to show that V = IVjjfc+n-i.

4

By direct computations, if = 5, then { ips5+„{Ji) '■ 1 < ^ < 4 } = { J4, J2 + J3, Ji, E +

i=l

22

[5, 55+n(5)] }(1V. If A; = 6, then { <^^,^„( J^) : 1 < ^ < 5 } = { E + [6, 56+n(6)], Ji + J2 +

5

J3, ^4 + ^5, ^2 + ^3 + ^4 + J5, + E + [6, 56+n(6)] + <^56+„([6, 56+n(6)]) } C If > 7, then,

1=1

3 fc-1

since <pSk+n{Y^ Ji) = Ji and fSk+niY^ Ji) = Ji + [k, h+nik)], we easily obtain that

i=l i=l i=4 i=l

fc-1 fc-1

n

(Ji) = ^Ji e < Ji, J2 + J3,X]'^^'l^'^fc+"(^)] >'

i=4 i=4
3 fc-1

'PSk+niJ^) ^^Ji ^ < Jl,J2 + J3,^Ji,[k,h+n{k)]>,

i=l i=4
fc-1 fc-1

k+'

„(J3) = ^Ji ^ < Jl,J2 + J3,^Ji,[k,Sk+n{k)]>,
1=4 1=4
3 fc-1 fe-1

+ + ^ < Jl, J2 + J3,Xl'^i'[^'<^fc+"(^)] > ■

i=l j=l i=4

Therefore, (fs~^^{Ji) G 1^ for alll < i < 4.

On the other hand, for /c > 7 and 2<i</c — 5, we have (p'^~^~\Jk-i) = J5 and, since

fc-1 fc-1

"pI+M^)) = J2 + Js + 'iJ^Ji e < Jl, J2 + Js: Ji^ ^k+n{k)] >,

1=4 i=4

3 fc-1

^S^+AJ2 + Ji) = Jl + J2 + J3, VS^+niYl '^^) = m

1=1 1=1

and

-fc-1 \ fc-1

J2J^) =J2J^ + [k,Sk+n{k)],
i=4 ^ i=l

we have = ^^I.K^J^s)) = ^s^SJ^ + ^3 + 2 E

i=4

fc-1

e < Ji, J2 + J3, XI ^i, [k, 5k+n{k)\,^p5k+n{[k, h+n{k)]), ■■■ , vtkjn^[k, Sk+n{k)]) > .

i=4

So, we inductively obtain that (pg~^^{Jk-i) G F for all 2 < i < /c - 5. That is, <Ps~_^^{Jj) £ V for
all 5 < j < A;-2. Finally, it is easy to see that (p'^~^JJk-i) = (pg^^JJk-2 + Jk-i + ik, Sk+n{k)]) =

+ Jk-1 + [K5k+n{k)\)) = <P\+SJ^ + Je + J7 + • • • + Jfc-1 + [K5k+n{k)\ +

fc-1 fc-5

^5,U[K h+n{k)]) + • • • + = ^1 + E + E ^'l.Jf/^, 5/i+n(A;)]) e

i=l i=0

23

Therefore, we have shown that V C W^k+n-i. Since, by Theorem 6, (fs^+n is an isomorphism
on W^k+n-i, {^Sk+n^"^^"^ : 1 < i < k + n — 1} is a, basis for l^^fc+n-i. Thus, V — W^k+n-i. In
particular, 5" is a basis for W^k+n-i.

Let h the the hnear isomorphism from Wjg^k+n-i onto itself defined by

'h{J,) = J,,
KJ2) = Ji + J2 + J3,

k—l
i=4

h{J4+i) = V5,+A^^ Sk+n{k)]), 0<i<k-5,
KJj)=v1:tSJj)^ k<j<k + n-l.

k~l

Now {h o (pp^^J{Ji) = h{J^) ^ Y.Ji^ VSk+SJ^) = {V5k+n° h){Ji), {ho ipp^^J{J2) =

k-l

KJ2 + J?,) = J1 + J2 + J3+J2 Ji = 'PPk+niJi + J^ + Js) = (<^/3,+„o/i)(^2), and (/io(^^^^J(J3) =

1=4

k-l k-l

h{J2+J3+J4) = J2+J3+J4+YI Ji+[k,5k+nik)] = ^pk+niYl Ji) = (<^5fc+„°^)(>^3)- Furthermore,

i=4 1=4

for < i < A; - 5, (/i o ^p^^J{J^+i) = h{J4+i+i) = 'fiZl^iik, Sk+n{k)]) = (<^4+„ o h){J4+i).

lik<j< k + n-1 and <Pp^,+„{Jj) = [s,t] C + then (pp^+„{Jj) = [/3fe+nO') : /3fc+n(i +

1)] = = : 4+n(i + 1)] = So, (/lO(^^,^J(J,.) = = ME^i) =

i=s

i=s i=s i=s

fSk+ni^i'^j)) — ifSk+n°^)i'^j)j where [a : b] denotes the closed interval with a and b as endpoints.

lfk<j<k + n— 1 and '^i3k_f_„{Jj) = [l,t] with k < t < k + n, then <^Sf.^„{Jj) =

[k-i,t]. So, {n,,„oh){j,) = vs,,MJj)) = V5,,sv]:ts-m = vX"Svs,,s.h)) =

i=k i=k i=k

^tliJk-2 + Jk-l^k,6kUm + E^ttiJ^) = JlHJl^

i=k j=4 i=0

+ E = ^(^1) + KJ2) + h(Js) + ■■■ + h(Jt-i) = h([i, t]) = (/i o

i=k

Therefore, we have shown that {h o (pi3^^^){Ji) = {fSk+„ ° h){Ji) for every integer 1 < i <
/c + n - 1. Thus, h o (^^^^^ = ip^^^^ o Oil Vl^]^fc + Ti— 1. Since h is an isomorphism from W^k+n-i
onto itself, this implies that </3/3j._,_„ is conjugate to <^5j._,_„ through /i. Consequently, the Petrie
matrix of Pk+n is similar to that of 5k+n- This shows that [3k and 5k are right similar.

Let ^k+2 and denote the cyclic permutations 1— s>4— s>3— s>5— i^6— s>7— ^^---^
A;-l^A;^A; + l^A; + 2^2^1andl^A; + l^A; + 2^A;^A;-l^A;-2^ >

24

7— >6^4-^3— s>5— s>2— s>lon Pk+2 respectively. By using elementary row operations, it is
easy to see that the determinant of the Petrie matrix of fik+2 is ( — 1)'^^^ while that of i'k+2 is
(— 1)'^. Since they are different, this shows that Pk and 6k are not two-sided similar.

Since the trace of the Petrie matrix of the cyclic permutation l-^4^3^5^6^
7^---^A; — l^A;^2^1is5 and that of the Petrie matrix of the cyclic permutation
1— >-fc—>A; — l^A; — 2^---^7^6^4^3^5^2^1is3, and 6k are not left
similar. ■

4 Equivalence classes of one-sided and two-sided simi-
larities in the symmetric group

In the symmetric group 5*3 of permutations on the set {1,2,3}, no pairs of permutations can
be one-sided similar or weakly similar while the pair {(123), (132)} is the only pair which is
two-sided similar. No other pairs are two-sided weakly similar.

5 Equivalence classes of one-sided and two-sided simi-
larities in the symmetric group 5*4

In the symmetric group S4 of permutations on the set {1,2,3,4}, the three pairs {(12), (23)},
{(123), (132)}, and {(1342), (1432)} are the only pairs which are right similar.

That the pair {(12), (23)} is right similar is depicted in the following Figure 13.

2

4

2

4

\

Figure 13: The permutations a and p are right similar.

25

That the pair {(123), (132)} is right similar is depicted in the following Figure 14.

1 3 4

2

3

4

P

\

\

Figure 14: The permutations a and p are right similar.

That the pair {(1342), (1432)} is right similar follows from Theorem 7.

By Theorem 3, the pairs {(1342), (1234)}, {(23), (34)}, and {(234), (243)} are the only pairs
which are left similar.

As for weakly similarities, the pairs {(34), (12)(34)}, {(142), (243)}, and the triple {(14)(23),
(14), (24)}, are the only permutations in 5*4 which are right weakly similar, but not right similar.

That the pair {(34), (12) (34)} is not right similar can be seen by considering the synchronized
right extension {cr^, p^) of o"4 and p4 on P5 with 0-5 = (345), ps = (12)(345). It is easy to check
that the minimal polynomial of Mo-5,4 is — 2x^ + 1 while that of Mpg^4 is x'^ — 3x^ + 2x^ + x — l.

To see that the pair {(142), (243)} is right weakly similar, let a = (142) and p = (243).
For any k > 5 and any synchronized right extension {(yk,Pk) of cr and p, let M{ak,k — 1\S)
{M{pk,k — 1\S) respectively) denote the matrix representing the linear transformation (p^^^
{ippf, respectively) on W^k-i with respect to the basis S = { J2, Ji, J2 + J3, Ja, J5, -hr ■ ■ , Jk-i}-
We then use Laplace's formula to expand the determinants det{M{ak, k — 1\S) — XI) and
det(M(pfc, k — l\S) — XI) along the first column to confirm that they have the same characteristic
polynomial.

To see that the triple {(14)(23), (14), (24)}, are right weakly similar to one another, let a =
(14)(23), p = (14), and 7 = (24). For any k > 5 and any synchronized right extension (0"^, pk, 7fc)
of a, p, and 7, let M{j3k,k — l\Sf3) denote the matrix representing the linear transformation
ipi3i^ on W^k-i with respect to the basis S'/3, where

Jk-i}, if P = a or P = p,

26

We then use Laplace's formula to expand the determinants det(M(afc, k — l\SaJ — XI) and
det{M(pk,k — l\Sp^,)—XI) along the first row and to the determinants det(M(pfe, k — l\Spf,) — XI)
and dct(M(7fc,/c — 1\S^^) — XI) along the first column to confirm that they have the same
characteristic polynomial.

Finally, as for the two-sided similarity or weak similarity, the pair {(134), (142)} and the
triple {(1234), (1432), (1342)} are the only permutations in 5*4 which are two-sided similar and
the pair {(23), (14) (23)} is the only pair in 5*4 which are two-sided weakly similar, but not
two-sided similar.

That the pair {(134), (142)} is two-sided similar can be seen as follows: Let (T4 = (134)
and p4 = (142). For any synchronized two-sided extension {(Tm+i+n, Pm+4+n) of 0-4 and p^, let

(m + 4)]

) V-'pm+4+n (■^"1+4)) ("^ni+s)!

'Ppm+4+niJm+6), ■■■ ,^prr,+i+Mm+2+n), ^pm+4+niJm+3+n)}- By mimicking the proofs as in the
previous theorems, we'll obtain the desired result. That the triple {(1234), (1432), (1342)} are
two-sided similar follows from Theorem 8.

That the pair {(23), (14) (23)} is two-sided weakly similar can be established by expanding
the determinants obtained with respect to the standard bases along the row which corresponds
to the basis element Jm+2-

References

[1] L. Alseda, J. Llibre and M. Misiurewicz, Combinatorial dynamics and entropy in dimension
one, second edition. Advanced Series in Nonlinear Dynamics, Vol. 5, World Scientific,
Singapore, 2000.

[2] S. Aronowitz and B. E. Eichinger, Petrie matrices and generalized inverses, J. Math. Phys.
16 (1975), 1278-1283.

[3] M. Artin and B. Mazur, On periodic points, Ann. Math. 81 (1965), 82-99.

[4] L. S. Block and W. A. Coppel, Dynamics in One Dimension, Lecture Notes in Math.,
1513, Springer- Verlag, Berlin, 1992.

[5] L. Block, J. Guckenheimer, M. Misiurewicz and L.-S. Young, Periodic points and topolog-
ical entropy of one-dimensional maps. Global theory of dynamical systems (Proc. Intemat.
Conf., Northwestern Univ., Evanston, III., 1979), Lecture Notes in Math., 819, Springer,
Berlin, 1980, pp. 18-34.

[6] M. Bona, Combinatorics of permutations, With a foreword by Richard Stanley, Discrete
Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL,
2004.

[7] Y. Cherniavsky and M. Sklarz, Conjugacy in permutation representations of the symmetric
group. Comm. Algebra 36 (2008), 1726-1738.

27

[8] B.-S. Du, Congruence identities arising from dynamical systems, Appl. Math. Letters 12
(1999), 115-119.

[9] B.-S. Du, The linearisations of cyclic permutations have rational zeta functions. Bull.
Austral. Math. Soc. 62(2000), 287-295.

[10] B.-S. Du, On the class of square Petrie matrices induced by cyclic permutations. Int. J.
Math. Math. Sci. 2004, no. 31, 1617-1622.

[11] W. Geller and J. Tolosa, Maximal entropy odd orbit types. Trans. Amer. Math. Soc. 329
(1992), 161-171.

[12] W. Geller and B. Weiss, Uniqueness of maximal entropy odd orbit types, Proc. Amer.
Math. Soc. 123 (1995), 1917-1922.

[13] W. Geller and Zhenhua Zhang, Maximal entropy permutations of even size, Proc. Amer.
Math. Soc. 126 (1998), 3709-3713.

[14] M. Gordon and W. T. Tutte, On sums of determinants of intersection matrices of Petrie
matrices, Proc. Cambridge Philos. Soc. 75 (1974), 155-163.

[15] M. Gordon and E. M. Wilkinson, Determinants of Petrie matrices. Pacific J. Math. 51
(1974), 451-453.

[16] I. N. Herstein, Topics in Algebra, first edition, Blaisdell Publ. Co., New York, 1964.

[17] D. M. King, Maximal entropy of permutations of even order, Ergod. Th. & Dynam. Sys.
17 (1997), 1409-1417.

[18] D. M. King and J. B. Strantzen, Maximum entropy of cycles of even period, Mem. Amer.
Math. Soc. 152 (2001), no. 723,

[19] J. Milnor and W. Thurston, On iterated maps of the interval. Dynamical systems ( College
Park, MD, 1986-87), 465-563, Lecture Notes in Math., 1342, Springer, Berlin, 1988.

[20] M. Misiurewicz and Z. Nitecki, Cominatorial patterns for maps of the interval, Mem. Amer.
Math. Soc. 94 (1991), no. 456.

28